#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL& x, LL& y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}

	LL x1, y1, d;
	d = exgcd(b, a % b, x1, y1);
	x = y1, y = x1 - a / b * y1;
	return d;
}
int main()
{

	return 0;
}